import java.util.HashMap;

/**
 * @author 汤奇
 * @version V1.0
 * @Project BookPro
 * @Package PACKAGE_NAME
 * @Description: 斐波那契数列
 * @Date 2022/7/27 20:49
 */
public class Test15 {
    public static void main(String[] args) {
        long strart = System.currentTimeMillis();
        System.out.print(f1(50));
        long end = System.currentTimeMillis();
        System.out.println("耗时:"+(end-strart));
    }

    private static long f(int n){
        if (n==1||n==2){
            return 1;
        }
        return f(n-1)+f(n-2);
    }

    /**
     * 缓存表优化递归
     */
    private static HashMap<Integer,Long> cache = new HashMap<>();
    private static long f1(int n){
        if (n==1||n==2){
            return 1;
        }
        if (cache.get(n) != null){
            return cache.get(n);
        } else {
            long result = f1(n-1)+f1(n-2);
            cache.put(n,result);
            return result;
        }
    }

    /**
     * 递归改造, 优化递归
     * @param n
     * @return
     */
    private static long f2(int n){
        if (n==1 || n==2){
            return 1;
        }
        long a = 1;
        long b = 2;
        long c = 0;
        for (int i = 0; i < n - 2; i++) {
            c = a+b;
            a=b;
            b=c;
        }
        return c;
    }
}
